//
//  QuickSort.swift
//  Chapter3LinkedList
//
//  Created by TRS-Mobile on 2021/9/3.
//

import Foundation

//快速排序

/// 选择元素count / 2为策略点的分区策略快速排序
/// - Parameter a: 数据
/// - Returns: 快速排序
func quickSortNaive<T: Comparable>(_ a: [T]) -> [T] {
    guard a.count > 1 else {
        return a
    }
    let pivot = a[a.count / 2]
    let less = a.filter { $0 < pivot }
    let equal = a.filter { $0 == pivot }
    let greater = a.filter { $0 > pivot }
    let merge = quickSortNaive(less) + equal + quickSortNaive(greater)
    print("-->: \(merge)")
    return merge
}


/// Lomuto快速排序
///
/// 该函数接受三个参数： a 是您要分区的数组。 低和高设置您将分区的阵列内的范围。 这个范围会随着每次递归而变得越来越小。 该函数返回枢轴的索引
/// - Parameters:
///   - a: 数据
///   - low: 分区范围低位
///   - high: 分区范围高位
/// - Returns: 枢轴的索引
func partitionLomuto<T: Comparable>(_ a: inout [T],
                                    low: Int,
                                    high: Int) -> Int {
    let pivot = a[high]
    var i = low
    for j in low..<high {
        if a[j] <= pivot {
            a.swapAt(j, i)
            i += 1
        }
    }
    a.swapAt(i, high)
    return i
}

func quickSortLomuto<T: Comparable>(_ a: inout [T],
                                    low: Int,
                                    high: Int) -> Void {
    if low < high {
        let pivot = partitionLomuto(&a, low: low, high: high)
        quickSortLomuto(&a, low: low, high: pivot - 1)
        quickSortLomuto(&a, low: pivot + 1, high: high)
        print(a)
    }
}

func partitionHoare<T: Comparable>(_ a: inout [T],
                                   low: Int,
                                   high: Int) -> Int {
    let pivot = a[low]
    var i = low - 1
    var j = high + 1
    while true {
        repeat { j -= 1 } while a[j] > pivot
        repeat { i += 1 } while a[i] < pivot
        if i < j {
            a.swapAt(i, j)
        } else {
            return j
        }
    }
}

func quickSortHoare<T: Comparable>(_ a: inout [T],
                                   low: Int,
                                   high: Int) {
    if low < high {
        let p = partitionHoare(&a, low: low, high: high)
        quickSortHoare(&a, low: low, high: p)
        quickSortHoare(&a, low: p + 1, high: high)
        print(a)
    }
}

/// 选择中位数作为支点分割策略
///
/// 理想的枢轴将在小于和大于分区之间均匀地分割元素。 选择已排序数组的第一个或最后一个元素作为主元，使 Quicksort 的性能与插入排序非常相似，从而导致 O(n²) 的最坏情况性能。 解决这个问题的一种方法是使用三支点选择策略的中位数。 在这里，您可以找到数组中第一个、中间和最后一个元素的中位数，并将其用作枢轴。 这可以防止您选择数组中最高或最低的元素。
/// - Parameters:
///   - a: 数据
///   - low: 低
///   - high: 高
func medianOfThree<T: Comparable>(_ a: inout [T],
                                  low: Int,
                                  high: Int) -> Int {
    let center = (low + high) / 2
    if a[low] > a[center] {
        a.swapAt(low, center)
    }
    if a[low] > a[high] {
        a.swapAt(low, high)
    }
    if a[center] > a[high] {
        a.swapAt(center, high)
    }
    return center
}

func quickSortMedian<T: Comparable>(_ a: inout [T],
                                    low: Int,
                                    high: Int) {
    if low < high {
        let pIdx = medianOfThree(&a, low: low, high: high)
        a.swapAt(pIdx, high)
        let pivot = partitionLomuto(&a, low: low, high: high)
        quickSortLomuto(&a, low: low, high: pivot - 1)
        quickSortLomuto(&a, low: pivot + 1, high: high)
    }
}

func partitionDutchFlag<T: Comparable>(_ a: inout [T],
                                       low: Int,
                                       high: Int,
                                       pivotIndex: Int) -> (Int, Int) {
    let pivot = a[pivotIndex]
    var smaller = low
    var equal = low
    var larger = high
    while equal <= larger {
        if a[equal] < pivot {
            a.swapAt(smaller, equal)
            smaller += 1
            equal += 1
        } else if a[equal] == pivot {
            equal += 1
        } else {
            a.swapAt(equal, larger)
            larger -= 1
        }
    }
    return (smaller, larger)
}

func quickSortDutchFlag<T: Comparable>(_ a: inout [T],
                                       low: Int,
                                       high: Int) {
    if low < high {
        let (middleFirst, middleLast) = partitionDutchFlag(&a, low: low, high: high, pivotIndex: high)
        quickSortDutchFlag(&a, low: low, high: middleFirst - 1)
        quickSortDutchFlag(&a, low: middleLast + 1, high: high)
        print(a)
    }
}
